import entity.CacheElement;
import entity.DoublyLinkedList;
import entity.LinkedListNode;

import java.util.Map;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * LRU缓存实现（最长时间未使用的元素将从缓存中逐出）
 *
 * @author Kewen-Du
 * @date 2022/10/13
 */
public class LRUCache<K, V> implements Cache<K, V> {

    //缓存容量
    private int size;
    //存储所有缓存单元的哈希表
    private Map<K, LinkedListNode<CacheElement<K, V>>> linkedListNodeMap;
    //存储所有缓存单元的双向链表
    private DoublyLinkedList<CacheElement<K, V>> doublyLinkedList;
    //可重入读写锁（线程可多次获取锁，读锁共享，写锁排它）
    private ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public LRUCache(int size) {
        this.size = size;
        this.linkedListNodeMap = new ConcurrentHashMap<>(size);
        this.doublyLinkedList = new DoublyLinkedList<>();
    }

    /**
     * 缓存更新
     * 0.写锁，禁止其他线程读写
     * 1.新增，生成新节点插入list头
     * 2.更新，删除旧节点，生成新节点插入list头，如果长度超出则驱逐list尾节点、
     * 3.final 更新Map
     *
     * @param key
     * @param value
     * @return
     */
    @Override
    public boolean put(K key, V value) {
        //写锁（其他线程不能读写，此线程可读可写）
        this.lock.writeLock().lock();
        try {
            CacheElement<K, V> item = new CacheElement<K, V>(key, value);
            LinkedListNode<CacheElement<K, V>> newNode;
            if (this.linkedListNodeMap.containsKey(key)) {
                LinkedListNode<CacheElement<K, V>> node = this.linkedListNodeMap.get(key);
                newNode = doublyLinkedList.updateAndMoveToFront(node, item);
            } else {
                if (this.size() >= this.size) {
                    this.evictElement();
                }
                newNode = this.doublyLinkedList.add(item);
            }
            if (newNode.isEmpty()) {
                return false;
            }
            this.linkedListNodeMap.put(key, newNode);
            return true;
        } finally {
            this.lock.writeLock().unlock();
        }
    }

    /**
     * 读缓存
     * 0.读锁
     * 1.从Map读取节点，删除旧节点，生成新节点（值相同）插入list头
     *
     * @param key
     * @return
     */
    @Override
    public Optional<V> get(K key) {
        this.lock.readLock().lock();
        try {
            LinkedListNode<CacheElement<K, V>> linkedListNode = this.linkedListNodeMap.get(key);
            if (linkedListNode != null && !linkedListNode.isEmpty()) {
                linkedListNodeMap.put(key, this.doublyLinkedList.moveToFront(linkedListNode));
                return Optional.of(linkedListNode.getElement().getValue());
            }
            return Optional.empty();
        } finally {
            this.lock.readLock().unlock();
        }
    }

    @Override
    public int size() {
        this.lock.readLock().lock();
        try {
            return doublyLinkedList.size();
        } finally {
            this.lock.readLock().unlock();
        }
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public void clear() {
        this.lock.writeLock().lock();
        try {
            linkedListNodeMap.clear();
            doublyLinkedList.clear();
        } finally {
            this.lock.writeLock().unlock();
        }
    }

    /**
     * +
     * 驱逐缓存元素
     * 0.写锁
     * 1.从双向链表移除尾节点
     * 2.从Map移除该缓存
     *
     * @return
     */
    private boolean evictElement() {
        this.lock.writeLock().lock();
        try {
            LinkedListNode<CacheElement<K, V>> linkedListNode = doublyLinkedList.removeTail();
            if (linkedListNode.isEmpty()) {
                return false;
            }
            linkedListNodeMap.remove(linkedListNode.getElement().getKey());
            return true;
        } finally {
            this.lock.writeLock().unlock();
        }
    }
}
